In [143]:
# LinkedList Node
class LLNode:
def __init__(self, value):
self.next = None
self.value = value
def __str__(self):
node = self
string = "Linked List:"
while node != None:
string = "{0} {1}".format(string, node.value)
node = node.next
return string
def append(self, value):
node = self
while node.next != None:
node = node.next
node.next = LLNode(value)
def delete(head, value):
curr = head
if curr.value == value:
head = curr.next
curr = None
return head
while curr.next != None:
if curr.next.value == value:
curr.next = curr.next.next
return head
curr = curr.next
return head
In [144]:
# Simple LinkedList implementation
linked_list = LLNode(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(2)
print(linked_list)
delete(linked_list, 2)
print(linked_list)
2.1
Write code to remove duplicates from an unsorted linked list.
FOLLOW UP - How would you solve this problem if a temporary buffer is not allowed?
In [145]:
def remove_duplicates(linked_list):
nodes_seen = set()
prev = None
curr = linked_list
while curr != None:
if curr.value in nodes_seen:
prev.next = curr.next
else:
nodes_seen.add(curr.value)
prev = curr
curr = curr.next
In [146]:
llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
remove_duplicates(llist)
print(llist)
In [147]:
def remove_duplicates_followup(linked_list):
curr = linked_list
while curr != None:
ahead = curr
while ahead.next != None:
if curr.value == ahead.next.value:
ahead.next = ahead.next.next
else:
ahead = ahead.next
curr = curr.next
In [148]:
llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
remove_duplicates_followup(llist)
print(llist)
2.2
Implement an algorithm to find the kth to last element of a singly linked list.
In [149]:
def find_kth_last(linked_list, k):
if k < 0:
return None
curr = linked_list
runner = linked_list.next
for i in range(1, k):
if runner == None:
if i == k:
return curr
else:
return None
runner = runner.next
while runner != None:
curr, runner = curr.next, runner.next
return curr
In [150]:
llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
node = find_kth_last(llist, 3)
print(node)
2.3
Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
EXAMPLE
Input: the node c from the linked list a->b->c->d->e
Result: nothing is returned but the new linked list looks like a->b->d->e
In [151]:
def remove_from_middle(node):
if (node == None) or (node.next == None):
return False
node.value = node.next.value
node.next = node.next.next
In [152]:
llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
node = llist.next.next.next.next.next
print(node)
remove_from_middle(node)
print(llist)